// quick sort
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        int l = head->val, r = head->val, pivot;
        ListNode *p = head, *q, *h1 = nullptr, *h2 = nullptr;
        while(p) l = min(l, p->val), r = max(p->val, r), p = p->next;
        if(l == r) return head;
        pivot = (l + r) >> 1;
        p = head;
        while(p){
            q = p->next;
            if(p->val <= pivot){
                p->next = h1;
                h1 = p;
            }else{
                p->next = h2;
                h2 = p;
            }
            p = q;
        }
        h1 = sortList(h1);
        h2 = sortList(h2);
        p = h1;
        while(p->next) p = p->next;
        p->next = h2;
        return h1;
    }
};

// merge sort
class Solution2 {
public:
    int getLength(ListNode *head){
        int n = 0;
        while(head) n++, head = head->next;
        return n;
    }

    ListNode *merge_sort(ListNode *head, int n){
        if(n <= 1) return head;
        int l = n / 2, r = n - l;
        ListNode *p = head, *p1, *p2, ret;
        for(int i = 1; i < l; i++) p = p->next;
        // point to the first chain header node
        p1 = head;
        // point to the second chain header node
        p2 = p->next;
        // disconnect listnode
        p->next = NULL;
        p1 = merge_sort(p1, l);
        p2 = merge_sort(p2, r);
        p = &ret;
        ret.next = NULL;
        while(p1 || p2){
            if(p2 == NULL || (p1 && p1->val <= p2->val)){
                p->next = p1;
                p = p1;
                p1 = p1->next;
            }else{
                p->next = p2;
                p = p2;
                p2 = p2->next;
            }
        }
        return ret.next;
    }    

    ListNode* sortList(ListNode* head) {
        int n = getLength(head);
        return merge_sort(head, n);
    }
};